#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

// 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
class MinStack
{
    // 辅助栈与元素栈同步插入与删除，用于存储与每个元素对应的最小值
    stack<int> x_stack;
    stack<int> min_stack;

public:
    MinStack()
    {
        // 初始化堆栈对象
        min_stack.push(INT_MAX);
    }

    void push(int val)
    {
        x_stack.push(val);
        min_stack.push(min(min_stack.top(), val));
    }

    void pop()
    {
        x_stack.pop();
        min_stack.pop();
    }

    int top()
    {
        return x_stack.top();
    }

    int getMin()
    {
        return min_stack.top();
    }
};

class MinStack1
{
    // 链表实现
    struct Node
    {
        int val; // 当前节点的值
        int min; // 当前以此节点为栈顶的栈内最小元素的值
        Node *next;
        Node(int x, int y) : val(x), min(y), next(nullptr) {}
    };
    Node *head; // 声明头节点

public:
    MinStack1()
    {
        head = nullptr;
    }

    void push(int x)
    {
        // 若栈空，则申请新节点空间并赋予头节点
        if (head == NULL)
        {
            head = new Node(x, x);
        }
        else
        {
            // 栈非空，则更新新节点的栈内元素最小值后，将新节点插入栈顶，最后更新头节点
            Node *cur = new Node(x, x < head->min ? x : head->min);
            cur->next = head;
            head = cur;
        }
    }

    void pop()
    {
        // 每个结点的min值记录的是栈底到此节点的元素最小值
        // 让头节点指向自身的下一个节点即可
        head = head->next;
    }

    int top()
    {
        return head->val;
    }

    int getMin()
    {
        return head->min;
    }
};
int main()
{
    MinStack1 *obj = new MinStack1();
    for (int i = 0; i <= 4; i++)
    {
        int val = i;
        obj->push(val);
    }

    int param_1 = obj->top();
    printf("top1:%d\n", param_1);
    param_1 = obj->getMin();
    printf("min1:%d\n", param_1);
    obj->pop();

    param_1 = obj->top();
    printf("top2:%d\n", param_1);
    param_1 = obj->getMin();
    printf("min2:%d\n", param_1);
    return 0;
}
